//
// Created by xili on 2024/7/31 20:48.
// Go big or go home.
//
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:
    //集合的代表元素
    vector<int> father;
    //是否知晓秘密
    vector<bool> secret;
public:
    vector<int> findAllPeople(int n, vector<vector<int>> &meetings, int firstPerson) {
        //构建
        build(n, firstPerson);
        //对会议按照时间进行排序
        sort(meetings.begin(), meetings.end(), [](const auto &a, const auto &b) { return a[2] < b[2]; });
        int l = 0, r;
        int m = meetings.size();
        while (l < m) {
            r = l;
            //按照时间从小到大分块
            while (r + 1 < m && meetings[l][2] == meetings[r + 1][2]) {
                r++;
            }
            //同一时间内的人
            for (int i = l; i <= r; i++) {
                setUnion(meetings[i][0], meetings[i][1]);
            }
            //拆分不知道秘密的人为单独的集合
            for (int i = l, a, b; i <= r; i++) {
                a = meetings[i][0];
                b = meetings[i][1];
                if (!secret[find(a)]) {
                    father[a] = a;
                }
                if (!secret[find(b)]) {
                    father[b] = b;
                }
            }
            l = r + 1;
        }
        //将知晓秘密的人加入答案数组中
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (secret[find(i)]) {
                ans.emplace_back(i);
            }
        }
        return ans;
    }

    //构建集合，和是否知晓秘密
    void build(int n, int first) {
        father.resize(n);
        secret.resize(n);
        for (int i = 1; i < n; i++) {
            father[i] = i;
            secret[i] = false;
        }
        secret[0] = true;
        father[first] = 0;
        secret[first] = true;
    }

    //扁平化处理
    int find(int p) {
        if (father[p] != p) {
            father[p] = find(father[p]);
        }
        return father[p];
    }

    //将两个不同的集合合并
    void setUnion(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
            secret[fy] = secret[fy] || secret[fx];
        }
    }
};